822. 翻转卡片游戏

Similar Question

Solution Tips

方案一: 哈希表 + 模拟

var flipgame = function(fronts, backs) {
    // 有点像动态规划, 但是情况讨论好复杂啊
    // 正面和背面是可以相互转换的, 只是代表着当前状态
    // 任意一张卡片数字, 都可以和其他所有的卡片的任意正反面组合
    // 唯一不能组合的就是自己的正反面
    // 如果要选第 0 张的话, 不可能, 因为正面与背面的数相同, 无论何时都会存在 fronts 含有与 backs[0] 相同
    // 所以, 所有的正反相同的卡片都不可能符合题意
    // 选第 1 张, 就是示例的情况, 如果不反转, 3 也是候选答案之一
    // 需要两个哈希表, 一个存储住正面, 一个存储反面
    let frontsMap = {};
    let backsMap = {};
    // init maps
    for (let i = 0; i < fronts.length; i++) {
        addNumber(fronts[i], backs[i]);
    }

    let res = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < fronts.length; i++) {
        if (fronts[i] === backs[i]) {
            continue;
        }


        // 0 or undefined, 背面的数字, 在正面没有
        if (!frontsMap[backs[i]]) {
            // 符合题意
            res = Math.min(res, backs[i]);
        }
        // 考虑反转当前的卡片
        // 因为这张卡片正面和反面都不相同, 而且反面的数字在正面没有
        // 如果正面的数字 hashMap 为 1 的话, 那就是仅有自己
        // 这个时候直接进行一次反转, 也是符合题意的答案
        // 没办法在一个 for 循环里把其他相同的卡片都反转
        // 反转所有的 fonts[i]

        const tempFrontsMap = { ...frontsMap };
        const tempBacksMap = { ...backsMap };
        let sameSide = false;
        for (let j = 0; j < fronts.length; j++) {
            // 如果有一张卡片正反面都与 fronts[i] 相同
            // 那么无论如何反转都不会符合题意直接退出
            if (fronts[j] === backs[j] && fronts[j] === fronts[i]) {
                sameSide = true;
                break;
            }

            if (fronts[j] === fronts[i]) {
                // 反转
                // [fronts[j], backs[j]] = [backs[j], fronts[j]]
                // 更新 map
                frontsMap[fronts[j]]--;
                backsMap[backs[j]]--;
                addNumber(backs[j], fronts[j]);
            }
        }
        // 所有的与正面相同的卡片都反转到背面了, 检查是否符合题意
        if (sameSide) {
            // 还原 Map
            frontsMap = tempFrontsMap;
            backsMap = tempBacksMap;
            continue;
        };
        if (!frontsMap[fronts[i]]) {
            res = Math.min(res, fronts[i]);
        }

        // 还原 Map
        frontsMap = tempFrontsMap;
        backsMap = tempBacksMap;

    }

    return res === Number.MAX_SAFE_INTEGER ? 0 : res;


    function addNumber(front, back) {
        if (frontsMap[front] === undefined) {
            frontsMap[front] = 1;
        }
        else {
            frontsMap[front]++;
        }

        if (backsMap[back] === undefined) {
            backsMap[back] = 1;
        }
        else {
            backsMap[back]++;
        }
    }
};

// let fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
// let fronts = [1], backs = [1]
let fronts = [1,1,1,3,2,2,2,1,2,3]
let backs = [2,3,1,2,1,2,2,2,2,3]
console.log(flipgame(fronts, backs))

每一次考虑正面的时候, 反转所有相同的卡牌, 其实会有重复的工作. 这里可以用贪心算法小优化一下, 如有正反相同的卡牌, 后续遇到正反可以不用判断: banMap

考虑动态规划呢?

定义 dp[i] 为前 i 张卡片, 符合题意的值

只有正反小于 dp[i - 1] 才有反转的价值, 那还是得反转, 只能小优化一下

Map 的还原能否优化一下?

方案二: 脑筋急转弯 + 思路清晰版

如果一张卡片正反两面有相同的数字，那么这张卡片无论怎么翻转，正面都是这个数字，这个数字即不能是最后所选的数字 x。

按照这个思路，我们首先遍历所有卡片，如果卡片上的两个数字相同，则加入哈希集合 same 中，除此集合外的所有数字，都可以被选做 x， 我们只需要再次遍历所有数字，找到最小值即可。

最后，我们返回找到的最小值，如果没有则返回 0。

var flipgame = function(fronts, backs) {
    const same = new Set();
    for (let i = 0; i < fronts.length; i++) {
        if (fronts[i] === backs[i]) {
            same.add(fronts[i]);
        }
    }
    let res = 3000;
    for (let x of fronts) {
        if (x < res && !same.has(x)) {
            res = x;
        }
    }
    for (let x of backs) {
        if (x < res && !same.has(x)) {
            res = x;
        }
    }
    return res % 3000;
};